package com.cn.httptest;

/* 
 * Java实现快速排序算法 
 * 由大到小排序 
 * author:wyr 
 * 2016-7-14 
 *两个步骤：1，建堆  2，对顶与堆的最后一个元素交换位置 
 */
public class HeapSort {

	public static void main(String[] args) {
		int a[] = { 3, 1, 5, 7, 2, 4, 9, 6, 10, 8, 3 };
		HeapSort obj = new HeapSort();
		System.out.println("初始值：");
		obj.print(a);

		for (int i = 0; i < a.length; i++) {
			// obj.createLittleHeap(a, a.length - 1 - i);//
			// 创建堆,创建的是小顶堆。每次循环完，二叉树的根节点都是最小值，所以与此时的未排好部分最后一个值交换位置
			obj.myCreateLittleHeap(a, a.length - 1 - i);
			obj.swap(a, 0, a.length - 1 - i);// 与最后一个值交换位置，最小值找到了位置
			obj.print(a);
			System.out.println();

		}

		System.out.println("\n排序后：");
		obj.print(a);

	}

	/*
	 * 创建小顶堆：双亲节点小于子节点的值。从叶子节点开始，直到根节点。这样建立的堆定位最小值
	 */
	private void createLittleHeap(int[] data, int last) {
		for (int i = (last - 1) / 2; i >= 0; i--) { // 找到最后一个叶子节点的双亲节点
			// 保存当前正在判断的节点
			int parent = i;
			// 若当前节点的左子节点存在，即子节点存在
			while (2 * parent + 1 <= last) {
				// biggerIndex总是记录较大节点的值,先赋值为当前判断节点的左子节点
				int small = 2 * parent + 1;// bigger指向左子节点
				if (small < last) { // 说明存在右子节点

					if (data[small] > data[small + 1]) { // 右子节点>左子节点时

						small = small + 1;
					}
				}
				if (data[parent] > data[small]) { // 若双亲节点值大于子节点中最小的
					// 若当前节点值比子节点最小值大，则交换2者得值，交换后将smallIndex值赋值给k
					swap(data, parent, small);
					parent = small;
				} else {
					break;
				}
			}
		}
	}

	public void myCreateLittleHeap(int[] a, int last) {

		for (int i = (last - 1) / 2; i >= 0; i--) {

			int parent = i;

			// 当节点存在子节点时，需要进行判断调整树
			while (parent * 2 + 1 <= last) {

				int small = parent * 2 + 1; // 设节点的左子节点为最小值

				if (small + 1 <= last) { // 说明存在右节点
					if (a[small] > a[small + 1]) { // 右节点比左节点数值小
						small = small + 1;
					}
				}

				if (a[parent] > a[small]) {
					swap(a, parent, small);
					parent = small;
				} else {
					break; // 没有产生调整，直接跳出while
				}

			}

			
		}

	}

	public void print(int a[]) {
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
	}

	public void swap(int[] data, int i, int j) {
		if (i == j) {
			return;
		}
		data[i] = data[i] + data[j];
		data[j] = data[i] - data[j];
		data[i] = data[i] - data[j];
	}
}
